package com.grakol.parallel.samples.tests;

import java.util.List;

import com.grakol.parallel.samples.IFunction;

/**
 * Computes Fibonacci numbers;
 * 
 * @author LK
 */
public class FibonacciFunction implements IFunction<Long> {
	// attributes
	private boolean _iterative = false;
	private long _inputNo;
	private long _threshold;
	private Long _result;
	
	public FibonacciFunction( long inputNo ) {
		if( inputNo < 0 )
			throw new IllegalArgumentException( "invalid input number" );
		_inputNo = inputNo;
	}

	public FibonacciFunction( long inputNo, long threshold ) {
		this( inputNo );
		if( threshold >= inputNo )
			throw new IllegalArgumentException( "invalid threshold" );
		_threshold = threshold;
	}
	
	public FibonacciFunction( long inputNo, boolean iterative ) {
		this( inputNo );
		_iterative = iterative;
	}
	
	@Override
	public void perform() {
		_result = _threshold > 0 ? fibonacciNumberRecursive( _inputNo, _threshold ) 
					: _iterative ? fibonacciNumberIterative( _inputNo ) 
							: fibonacciNumberRecursive( _inputNo );
	}

	@Override
	public Long getResult() {
		return _result;
	}
	
	@Override
	public Long mergeResults( List<Long> results ) {
		Long mResult = null;
		switch( results.size() ) {
			case 2: 
				if( _threshold > 0 ) {
					// F(n) = F(m+1)F(n-m)+F(m)F(n-m-1), m < n;
					long m = _inputNo - _threshold;
					mResult = fibonacciNumberRecursive( m + 1 )*results.get( 0 ) 
								+ fibonacciNumberRecursive( m )*results.get( 1 );
				} else // F(n) = F(n-1) + F(n-2);
					mResult = results.get( 0 ) + results.get( 1 );
				break;
		}
		return mResult;
	}
	
	// Recursive Fibonacci algorithm
	public static long fibonacciNumberRecursive( long number ) {
		if( number < 0 )
			throw new IllegalArgumentException( "number < 0" );
		return number <= 1 ? number 
				: fibonacciNumberRecursive( number - 2 ) + fibonacciNumberRecursive( number - 1 );
	}

	// Alternative recursive Fibonacci algorithm
	public static long fibonacciNumberRecursive( long number, long threshold ) {
		if( number < 0 )
			throw new IllegalArgumentException( "number < 0" );
		long m = number - threshold;
		if( m < 1 ) // optimization does not make sense
			return fibonacciNumberRecursive( number );
		else // F(n) = F(m+1)F(n-m)+F(m)F(n-m-1), m < n;
			return fibonacciNumberRecursive( m + 1 )*fibonacciNumberRecursive( number - m ) 
					+ fibonacciNumberRecursive( m )*fibonacciNumberRecursive( number - m - 1 );
	}
	
	// Iterative Fibonacci algorithm
	public static long fibonacciNumberIterative( long number ) {
		if( number < 0 )
			throw new IllegalArgumentException( "number < 0" );
		if( number < 2 )
			return number;
		long fn = 1, fn_1 = 1, fn_2 = 0;
		for( long l = 2; l <= number; l++ ) {
			fn = fn_2 + fn_1;
			fn_2 = fn_1;
			fn_1 = fn;
		}
		return fn;
	}
	
}
